As one of techniques for data compression, there is what is called a sliding dictionary method (LZ77: Lempel-Ziv coding 1977). In the encoding (data compression) based on the sliding dictionary method, a buffer of predetermined length is regarded as a window. A data stream is input and output to/from the buffer in a FIFO (First-In First-Out) manner to slide the window frame. A longest-matching code string pattern is detected within the window frame, and the position information and the number of codes on the matching code string are encoded for data compression.
FIG. 4 shows an example of the data compression based on the sliding dictionary method. Suppose that a data stream “abcdebcd” is input. The code string from the top of the input stream to “abcde” is composed of different codes. The subsequent “bcd,” on the other hand, is composed of the same codes as ones included in the prior code string “abcde.”
When the foregoing input stream is compressed by the sliding dictionary method, as shown in FIG. 4, a reference code consisting of reference position (Ref) “0” and reference length (L) “5” is output for the leading code “abcde,” followed by the original non-reference code “abcde.” The reference position indicates the position of the dictionary (code) to be referred to. The leading “abcde” in this example consists of respectively different codes, and includes no candidate to be referred to. The reference position is thus set to “0.”
When the subsequent code string “bcd” is compressed, the previously processed “abcde” is used as a dictionary. The dictionary “abcde” contains a candidate “bcd” to be referred to for the subsequent code string “bcd.” Here, as shown in FIG. 4, a reference code consisting of reference position “4,” which is the value of return (offset value) from the end of the dictionary to the reference start position, and reference length “3,” which is the number of codes of the reference candidate, is output instead of the original code string “bcd.”
FIG. 5 shows another example of the data compression based on the sliding dictionary method. In this example, the input stream is “abcdedededed.” For the code string from the top to “abcde,” a reference code consisting of reference position “0” and reference length “5,” followed by the original code string “abcde,” is output as in the foregoing example (FIG. 4).
For the subsequent code string “dededed,” the reference position is determined to be “2” since the first “de” is included in the code string “abcde” as the dictionary. For the remaining “deded,” a setting is made such that the second “de” and the third “d” are referred to in succession after the first “de” is referred to, as shown in FIG. 5. For such a setting, the reference length is determined to be “7” which is the total number of “dededed.” As a result, a reference code consisting of reference position “2” and reference length “7” is output instead of the original code string “dededed.”
If a reference code is such that [reference position] is smaller than [reference length] ([reference position]<[reference length]) as in the example of FIG. 5, the reference code is decoded by repeating the processing of creating a result of decoding by referring to a previously-decoded code string, and then creating a new result of decoding by referring to the result of decoding. That is, the decoding is performed by a procedure reverse to the shown compression procedure. The codes are thus restored as much as the reference length set at compression time.
As described above, according to the sliding dictionary method, codes that occur a plurality of times in the input stream are converted into a reference code consisting of a reference position and a reference length upon the second and subsequent occurrences. The stream can thus be reduced in data volume.
To decode a compressed stream, on the other hand, entire preceding data need to have been decoded in advance even if the decoding of the stream is from a midpoint. Such a restriction produces the problem that the decoding takes a long time in applications where large data is decoded only in part.
An example of the techniques for avoiding such a situation is the compression method described in PTL 1. The compression method in the literature includes dividing an input stream into blocks of appropriate size, and performing data compression by the sliding dictionary method in each block.